Computer systems (and related devices) typically create three-dimensional images using a sequence of stages known as a graphics pipeline. During early pipeline stages, images are modeled using a mosaic-like approach where each object is composed of a collection of individual points, lines and polygons. These points, lines and polygons are known as primitives and a single image may require thousands, or even millions, of primitives. Each primitive is defined in terms of its shape and location as well as other attributes, such as color and texture.
The graphics pipeline maps, or renders, each primitive into a memory storage device known as a frame buffer. Each storage location within the frame buffer defines one pixel within the image being produced. The graphics pipeline performs the rendering process by determining which pixels (i.e., which frame buffer storage locations) are included within each primitive. Each pixel is then initialized to reflect the attributes of the primitive, or primitives in which it is included. In many cases, the graphics pipeline will further modify the pixel values in the frame buffer to apply texture, lighting and other effects to the graphics primitives.
The task of rendering primitives to pixels can be very time consuming. This is especially true for complex images that include many primitives or require complex lighting, shading or other effects. The time consumed transforming primitives becomes problematic for applications, such as flight simulators and virtual reality environments, where rapid image generation is required.
Occlusion culling methods attempt to improve the speed of the rendering process. For methods of this type, the rendering process is modified to take advantage of the fact that images often contain overlapping objects. This overlap means that some of the objects within an image may be fully or partially hidden or occluded. Occlusion culling methods detect occluded objects and eliminate them from all or part of the rendering process. In theory, this decreases the complexity of the rendering task and improves graphics throughput.
For maximum effectiveness, it is generally desirable to perform occlusion culling during the early stages of a graphics pipeline. Early occlusion culling maximizes the number of pipeline stages that benefit from the culling process. For this reason, many traditional occlusion culling methods, which only operate during the final pipeline stages, are far less than optimal. Unfortunately, traditional methods for early detection of occluded objects are often quite slow. As a result, the time gained by occlusion culling is often overshadowed by the time spent performing the culling process.
For these reasons, there is a need for improved occlusion culling methods. Preferably, methods of this type should be applicable to the early stages within a graphics pipeline. Methods of this type must operate quickly and ensure that time gained during the rendering process is not lost during the occlusion culling process.